package yz.com.javautil.roadNetwork;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

/**
 * 寻路（遍历全部路径）
 * 参考资料：https://www.runoob.com/data-structures/graph-theory-path.html
 *
 * @author runoob
 */
public class AllPath {
    /**
     * 图的引用
     */
    private Graph graph;
    /**
     * 起点
     */
    private int startPoint;
    /**
     * 终点
     */
    private int endPoint;
    /**
     * 记录dfs的过程中节点是否被访问
     */
//    private boolean[] visited;
    /**
     * 记录路径, from[i]表示查找的路径上i的上一个节点
     */
    private int[] from;
    /**
     * 记录全部可达路径
     */
    private List<Vector<Integer>> allPathList = new ArrayList<>();

    /**
     * 构造函数
     * 寻路算法(寻找图 graph 从 startPoint 点到 endPoint 点的全部路径)
     *
     * @param graph      图对象
     * @param startPoint 起点
     * @param endPoint   终点
     */
    public AllPath(Graph graph, int startPoint, int endPoint) {
        // 算法初始化
        this.graph = graph;
        assert startPoint != endPoint;
        assert startPoint >= 0 && startPoint < this.graph.getNodeNum();
        boolean[] visited = new boolean[this.graph.getNodeNum()];
        from = new int[this.graph.getNodeNum()];
        for (int i = 0; i < this.graph.getNodeNum(); i++) {
            visited[i] = false;
            from[i] = -1;
        }
        this.startPoint = startPoint;
        // 寻路算法
        dfs(visited, startPoint, endPoint);
    }

    /**
     * 图的深度优先遍历
     *
     * @param vertex 顶点
     */
    private void dfs(boolean[] visited, int vertex, int endPoint) {
        if (vertex == endPoint) {
            Stack<Integer> stackPath = new Stack<>();
            // 通过from数组逆向查找到从s到w的路径, 存放到栈中
            int p = endPoint;
            while (p != -1) {
                stackPath.push(p);
                p = from[p];
            }
            // 从栈中依次取出元素, 获得顺序的从s到w的路径
            Vector<Integer> res = new Vector<>();
            while (!stackPath.empty()) {
                res.add(stackPath.pop());
            }
            allPathList.add(res);
            // 清理状态
        }

        visited[vertex] = true;
        Vector<Integer> adjacentEdge = graph.getAdjacentEdge(vertex);
        for (int point : adjacentEdge) {
            boolean[] visitedIn = visited.clone();
            if (!visited[point]) {
                from[point] = vertex;
                dfs(visitedIn, point, endPoint);
            }
        }
    }

    /**
     * 返回从s点到w点的路径
     */
    public List<Vector<Integer>> getAllPath() {
        return allPathList;
    }
}
